/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void swap(ListNode *&node1, ListNode *&node2)
{
    ListNode *tmp = node1;
    node1 = node2;
    node2 = tmp;
}

void swap(int &node1, int &node2)
{
    int tmp = node1;
    node1 = node2;
    node2 = tmp;
}

class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB末尾对齐的位置，
        int lenA = 0;
        int lenB = 0;
        ListNode *curA = headA;
        ListNode *curB = headB;
        while (curA != nullptr)
        {
            lenA++;
            curA = curA->next;
        }

        while (curB != nullptr)
        {
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;

        if (lenB > lenA)
        {
            swap(curA, curB);
            swap(lenA, lenB);
        }
        int gap = lenA - lenB;
        while (gap--)
        {
            curA = curA->next;
        }

        while (curA != nullptr)
        {
            if (curA == curB)
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;

        // 此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
        // 否则循环退出返回空指针。
    }
};
